 //2385.感染二叉树需要的总时间
 //https://leetcode.cn/problems/amount-of-time-for-binary-tree-to-be-infected/?envType=daily-question&envId=2024-04-24
class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        queue<TreeNode*> q;
        unordered_map<int,vector<int>> hash;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* nd = q.front(); q.pop();
            if(nd->left)
            {
                hash[nd->val].push_back(nd->left->val);
                hash[nd->left->val].push_back(nd->val);
                q.push(nd->left);
            }
            if(nd->right)
            {
                hash[nd->val].push_back(nd->right->val);
                hash[nd->right->val].push_back(nd->val);
                q.push(nd->right);
            }
        }

        queue<pair<int,int>> pq;
        unordered_set<int> visit;
        pq.push({start,0});
        visit.insert(start);
        int ret = 0;
        while(!pq.empty())
        {
            int nodeVal = pq.front().first;
            ret = pq.front().second;
            pq.pop();
            for(int& childVal:hash[nodeVal])
            {
                if(visit.count(childVal) == 0)
                {
                    pq.push({childVal,ret+1});
                    visit.insert(childVal);
                }
            }
        }
        return ret;
    }
};